package com.example.demo.algorithm;

import java.util.Arrays;
import java.util.Random;

/**
 * 项目名称：hell0-6
 * 类 名 称：QuickSort2
 * 类 描 述：
 * 创建时间：2020/12/13 15:55
 * 创 建 人：wangsheng
 */
public class QuickSort {

    public static void main(String[] args) {
        //先定义要排序的数组
        int[] arr = new int[100000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new Random().nextInt(1000000000) + 0;
        }
        long startTime = System.currentTimeMillis();
        sort(arr);
        long endTime = System.currentTimeMillis();
        long times = endTime - startTime;
        System.out.println("归并排序耗时：" + times);
//        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] a) {
        int L = 0;
        int R = a.length - 1;
        sort(a, L, R);
    }

    private static void sort(int[] a, int L, int R) {
        if (R <= L) {
            return;
        }
        //对a数组中，从L到R的元素进行切分
        int partition = partition(a, L, R);
        //对左边分组中的元素进行排序
        //对右边分组中的元素进行排序
        sort(a, L, partition - 1);
        sort(a, partition + 1, R);
    }

    public static int partition(int[] a, int L, int R) {
        int key = a[L];//把最左边的元素当做基准值
        int left = L;//定义一个左侧指针，初始指向最左边的元素
        int right = R + 1;//定义一个右侧指针，初始指向左右侧的元素下一个位置
        //进行切分
        while (true) {
            //先从右往左扫描，找到一个比基准值小的元素
            while (a[--right] > key) {//循环停止，证明找到了一个比基准值小的元素
                if (right == L) {
                    break;//已经扫描到最左边了，无需继续扫描
                }
            }
            //再从左往右扫描，找一个比基准值大的元素
            while (a[++left] < key) {//循环停止，证明找到了一个比基准值大的元素
                if (left == R) {
                    break;//已经扫描到了最右边了，无需继续扫描
                }
            }
            if (left >= right) {
                //扫描完了所有元素，结束循环
                break;
            } else {
                //交换left和right索引处的元素
                exch(a, left, right);
            }
        }
        //交换最后rigth索引处和基准值所在的索引处的值
        exch(a, L, right);
        return right;//right就是切分的界限
    }

    /*
    数组元素i和j交换位置
    */
    private static void exch(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

}
